package com.leetcode;

/**
 * @author fy
 * @date 2022/3/29 17:52
 */
public class Solution63 {

    /**
     * 63. 不同路径 II
     *
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] d = new int[][]{{-1, 0}, {0, -1}};

        int[][] count = new int[m][n];
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 1) {
                count[0][i] = 0;
            } else if (i > 0 && count[0][i - 1] == 0) {
                count[0][i] = 0;
            } else {
                count[0][i] = 1;
            }
        }
        for (int j = 1; j < m; j++) {
            if (obstacleGrid[j][0] == 1) {
                count[j][0] = 0;
            } else if (count[j - 1][0] == 0) {
                count[j][0] = 0;
            } else {
                count[j][0] = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    count[i][j] = 0;
                } else {
                    count[i][j] = count[i - 1][j] + count[i][j - 1];
                }
            }
        }
        return count[m - 1][n - 1];
    }

    private boolean inArea(int m, int n, int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0) {
            return 0;
        }

        // 定义 dp 数组并初始化第 1 行和第 1 列。
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
            dp[0][j] = 1;
        }

        // 根据状态转移方程 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 进行递推。
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        int[][] obstacleGrid = new int[][]{{0, 0, 0}, {1, 1, 0}, {0, 0, 0}};
//        new Solution63().uniquePathsWithObstacles(obstacleGrid);
        new Solution63().uniquePathsWithObstacles1(obstacleGrid);
    }

}
